package 力扣91;

/**
 * @ClassName : Day_16_513_找树左下角的值
 * @Author : 骆发茂
 * @Date: 2021/12/27 11:47
 * @Description : https://leetcode-cn.com/problems/find-bottom-left-tree-value/
 * https://leetcode-cn.com/problems/find-bottom-left-tree-value/solution/513-zhao-shu-zuo-xia-jiao-de-zhi-bfs-dfs-aawe/
 */
public class Day_16_513_找树左下角的值_dfs {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    /**
     * 思路二：DFS
     * 只有叶子节点可能是需要的返回值res  是可能需要返回的，不一定是，很多叶子节点，但不一定符合最终需要返回的
     * 所以递归的中止条件为当遇到叶子节点才return
     * 只有当前叶子节点的深度比之前的更大，才更新res
     * PS：因为要大于才会更新，所以每一层只会更新一次，先会遍历到左边的节点，所以只会更新每层最左侧的节点，符合题目要求
     * 因为要比较深度，在递归中除了节点作为参数外，还需要增加深度参数
     * 在res中增加一项专门用于存储深度， 即 res = [叶子节点值，叶子节点深度]
     * 最后返回的是res[0]
     * <p>
     * 作者：edelweisskoko
     * 链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value/solution/513-zhao-shu-zuo-xia-jiao-de-zhi-bfs-dfs-aawe/
     */
    class Solution {
        //复杂度分析
        //
        //时间复杂度：O(n)
        //空间复杂度：O(height)
        int[] res;

        public int findBottomLeftValue(TreeNode root) {
            //在res中增加一项专门用于存储深度， 即 res = [叶子节点值，叶子节点深度]
            //res的第一个是存节点的值，第二个是节点的深度，专门存储当前已知的最下，最左的节点
            //最后只需要返回res[0]
            res = new int[]{0, -1};
            dfs(root, 0);
            return res[0];

        }

        private void dfs(TreeNode node, int level) {
            //是叶子节点
            if (node.left == null && node.right == null) {
                //是叶子节点，而且深度比当前在res更深
                if (level > res[1]) {
                    //更新res
                    res[0] = node.val;
                    res[1] = level;
                }
            }
            //递归
            if (node.left != null) {
                dfs(node.left, level + 1);
            }
            //递归
            if (node.right != null) {
                dfs(node.right, level + 1);
            }

        }
    }
}